package ysf.com.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author ysf
 * @version 1.0
 * @date 2021/12/11 14:17
 * 希尔排序
 *
 */
public class ShellSort {

    public static void main(String[] args) {


        int[] datas = {10, 5, 9, 6, 7};
        System.out.println(JSON.toJSONString(datas));
        testShellSort(datas);
        System.out.println(JSON.toJSONString(datas));

    }

    /**
     * 希尔排序
     *
     * @param arr
     */
    public static void testShellSort(int[] arr) {
        // gap 为步长 每次减为原来的一半
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 对每一组都执行直接插入排序
            for (int i = 0; i < gap; i++) {

                // 对本组数据执行直接插入排序
                for (int j = i + gap; j < arr.length; j += gap) {
                    // 如果 a[j] < a[j-gap],则寻找a[j] 位置，并将后面数据的位置都后移
                    if (arr[j] < arr[j - gap]) {
                        int k;
                        int temp = arr[j];
                        for (k = j - gap; k >= 0 && arr[k] > temp; k -= gap) {
                            arr[k + gap] = arr[k];
                        }
                        arr[k + gap] = temp;
                    }
                }
            }
        }
    }


}
